표준 라이브러리(STL)

컨테이너는 객체를 저장하고 관리하는 자료 구조를 추상화한 클래스 템플릿이다. 표준 라이브러리(STL)의 핵심 구성 요소 중 하나로, 메모리 관리와 요소 접근을 위한 일관된 인터페이스를 제공한다. 컨테이너는 저장하는 요소의 타입에 대해 일반화되어 있어, 어떠한 자료형의 객체도 담을 수 있다는 특징을 가진다.

컨테이너는 크게 세 가지 범주로 분류된다. 첫 번째는 시퀀스 컨테이너로, 요소들이 선형적인 순서를 유지하며, 특정 위치에 요소를 삽입하거나 삭제하는 연산을 제공한다. 대표적으로 벡터, 리스트, 덱 등이 이에 속한다. 두 번째는 연관 컨테이너로, 키를 기반으로 요소에 빠르게 접근할 수 있도록 설계되었다. 요소의 순서는 키의 비교에 의해 결정되며, 집합, 맵, 멀티셋, 멀티맵 등이 있다. 세 번째는 컨테이너 어댑터로, 기존 컨테이너의 인터페이스를 제한하거나 변형하여 특정 목적에 맞게 동작하도록 한다. 스택, 큐, 우선순위 큐가 대표적이다.

모든 표준 컨테이너는 일련의 공통 멤버 함수와 타입 정의를 통해 통일된 사용법을 제공한다. 여기에는 컨테이너의 크기를 반환하는 size(), 컨테이너가 비었는지 확인하는 empty(), 요소를 삽입하는 insert(), 요소를 삭제하는 erase() 함수 등이 포함된다. 또한, 반복자를 생성하는 begin()과 end() 함수를 제공하여 컨테이너의 모든 요소를 순회할 수 있도록 지원한다.

이러한 설계는 알고리즘과 컨테이너를 완전히 분리시켜, 서로 독립적으로 개발하고 재사용할 수 있게 한다. 제네릭 프로그래밍의 원칙을 따르는 이 방식은 C++ 프로그래밍에서 높은 수준의 추상화와 코드 재사용성을 실현하는 데 기여한다.

알고리즘은 표준 라이브러리(STL)의 핵심 구성 요소 중 하나로, 컨테이너에 저장된 데이터에 대해 일반적인 연산을 수행하는 함수 템플릿들의 집합이다. 이들은 반복자를 통해 컨테이너와 독립적으로 동작하도록 설계되어, 다양한 종류의 자료 구조에 동일한 알고리즘을 적용할 수 있는 높은 재사용성과 유연성을 제공한다.

주요 알고리즘은 크게 검색, 정렬, 수치 연산, 집합 연산, 수정 연산 등으로 분류된다. 대표적인 예로는 특정 값을 찾는 find, 범위를 정렬하는 sort, 요소들을 변환하는 transform, 조건을 만족하는 요소를 제거하는 remove_if 등이 있다. 이러한 알고리즘들은 대부분 <algorithm> 헤더 파일에 정의되어 있으며, <numeric> 헤더에는 수치 관련 알고리즘이 포함되어 있다.

STL 알고리즘의 가장 큰 특징은 컨테이너의 내부 구조나 구현 방식에 의존하지 않는다는 점이다. 알고리즘 함수는 반복자 쌍(시작과 끝)을 인자로 받아 해당 범위 내의 요소들에만 접근하여 작업을 수행한다. 이는 데커레이터 패턴이나 전략 패턴과 같은 설계 원칙을 바탕으로, 데이터 구조와 알고리즘을 효과적으로 분리한 것이다.

또한, 많은 알고리즘은 사용자가 정의한 조건을 인자로 받을 수 있도록 설계되어 있다. 이는 함수 객체나 람다 식을 인자로 전달하여 알고리즘의 동작을 세밀하게 제어할 수 있게 하며, C++ 템플릿과 결합되어 강력한 제네릭 프로그래밍 패러다임을 실현한다.

반복자는 C++ 표준 라이브러리의 핵심 구성 요소 중 하나로, 컨테이너에 저장된 요소들에 접근하고 순회하기 위한 일반화된 방법을 제공하는 객체이다. 반복자는 포인터와 유사한 인터페이스를 가지며, 컨테이너의 내부 구조와 무관하게 요소를 가리키고, 다음 요소로 이동하는 등의 연산을 수행할 수 있다. 이는 알고리즘과 컨테이너를 연결하는 접착제 역할을 하여, 서로 다른 자료 구조에 대해 동일한 알고리즘 코드를 사용할 수 있게 하는 제네릭 프로그래밍의 기반을 이룬다.

반복자는 기능과 지원하는 연산에 따라 다섯 가지 주요 범주로 분류된다. 입력 반복자와 출력 반복자는 순방향으로만 읽거나 쓰는 기본적인 기능을 제공한다. 순방향 반복자는 읽기와 쓰기를 모두 지원하며 여러 번 순회가 가능하다. 양방향 반복자는 순방향 반복자의 기능에 더해 역방향으로 이동(-- 연산자)할 수 있다. 가장 강력한 범주인 임의 접근 반복자는 포인터 산술 연산과 유사하게 임의의 위치로 즉시 이동할 수 있으며, 벡터와 배열 같은 컨테이너에서 사용된다.

알고리즘 라이브러리의 대부분의 함수는 특정 유형의 반복자를 요구하며, 이를 통해 동작한다. 예를 들어, std::sort 알고리즘은 임의 접근 반복자를 필요로 하여 리스트에는 직접 사용할 수 없지만, 벡터나 일반 배열에는 적용 가능하다. 이처럼 반복자 범주를 정의함으로써, 알고리즘은 필요한 최소한의 기능만을 요구하여 가능한 가장 넓은 범위의 컨테이너와 함께 동작할 수 있도록 설계되었다.

함수 객체는 C++ 표준 라이브러리의 핵심 구성 요소 중 하나로, 함수 호출 연산자 operator()를 오버로드한 클래스의 객체이다. 이는 일반 함수처럼 호출될 수 있지만, 상태를 저장할 수 있는 객체라는 점에서 일반 함수 포인터보다 더 유연한 기능을 제공한다. STL의 알고리즘들은 정렬, 검색, 변환 등의 작업을 수행할 때 사용할 비교 기준이나 연산을 함수 객체를 통해 전달받는다.

함수 객체는 크게 두 가지 범주로 나눌 수 있다. 하나는 비교 함수나 산술 연산을 수행하는 일반 함수 객체이며, 다른 하나는 람다 표현식이다. 람다 표현식은 C++11 표준부터 도입된 기능으로, 익명의 함수 객체를 간결하게 생성할 수 있는 문법을 제공한다. 이를 통해 알고리즘 호출 지점에서 바로 연산 로직을 정의할 수 있어 코드의 가독성과 유지보수성을 높인다.

함수 객체의 주요 장점은 인라인 확장이 가능하다는 점이다. 함수 포인터를 사용할 경우 컴파일러의 최적화가 제한될 수 있지만, 함수 객체는 컴파일 타임에 그 타입이 알려져 있기 때문에 호출이 인라인화되기 쉽다. 이는 특히 STL 알고리즘과 같이 작은 연산이 반복적으로 수행되는 경우 성능 상의 이점으로 이어진다. 또한 템플릿과 결합되어 다양한 타입에 대해 동일한 인터페이스로 동작하는 제네릭 프로그래밍을 가능하게 한다.

할당자는 메모리의 동적 할당과 해제를 관리하는 객체이다. 표준 라이브러리(STL)의 컨테이너들은 내부적으로 메모리 할당을 위해 할당자를 사용하며, 이를 통해 메모리 관리 방식을 사용자 정의할 수 있다. 모든 표준 컨테이너는 std::allocator를 기본 할당자로 사용하도록 템플릿 매개변수로 정의되어 있다.

할당자의 주요 목적은 메모리 할당의 세부 구현을 추상화하여, 컨테이너가 특정 메모리 모델이나 풀 할당자와 같은 사용자 정의 할당 전략에 의존하지 않도록 하는 것이다. 사용자는 특정 요구사항에 맞춰 할당자를 직접 구현하거나 표준에서 제공하는 특수한 할당자를 사용할 수 있다. 이를 통해 성능 최적화나 공유 메모리와 같은 특수한 메모리 영역에서의 작업이 가능해진다.

할당자는 allocate, deallocate, construct, destroy와 같은 멤버 함수를 제공한다. 이 중 allocate와 deallocate는 순수한 메모리 할당과 해제를 담당하며, construct와 destroy는 할당된 메모리 공간에 객체를 생성하고 소멸시키는 역할을 한다. C++11 이후에는 상태를 가지는 할당자와 할당자 전파에 관한 규칙이 보다 명확히 정의되었다.

할당자의 사용은 주로 임베디드 시스템이나 고성능 컴퓨팅과 같이 메모리 사용에 엄격한 제약이나 특별한 최적화가 필요한 분야에서 두드러진다. 표준 라이브러리는 std::allocator 외에도 std::scoped_allocator_adaptor와 같은 어댑터를 제공하여 중첩된 컨테이너의 할당자 사용을 단순화한다.

시퀀스 컨테이너는 표준 라이브러리(STL)의 컨테이너 중 하나로, 요소들이 삽입된 순서대로 저장되는 선형적인 자료 구조이다. 이는 연관 컨테이너와 달리 요소의 위치가 값이 아닌 삽입 순서에 의해 결정된다는 특징을 가진다. 시퀀스 컨테이너는 메모리 상에서 연속적으로 배치되거나, 노드 기반으로 연결되는 등 내부 구현 방식에 따라 다양한 특성을 보인다.

주요 시퀀스 컨테이너로는 벡터, 리스트, 덱이 있다. 벡터는 동적 배열로 구현되어 임의 접근이 빠르고, 끝 부분에서의 삽입과 삭제가 효율적이다. 리스트는 이중 연결 리스트로 구현되어 컨테이너 내 어느 위치에서든 상수 시간에 삽입과 삭제가 가능하다. 덱은 벡터와 유사하지만 앞쪽과 뒤쪽 모두에서 효율적인 삽입과 삭제를 지원한다.

이 외에도 배열과 forward_list가 있다. 배열은 고정 크기의 시퀀스를 제공하며, 벡터와 달리 크기를 런타임에 변경할 수 없다. forward_list는 단일 연결 리스트로 구현되어 리스트보다 메모리 사용량이 적지만, 역방향 순회를 지원하지 않는다. 각 컨테이너는 서로 다른 알고리즘과 반복자 요구 사항을 가지며, 사용자는 수행할 작업의 특성에 따라 적절한 컨테이너를 선택해야 한다.

연관 컨테이너는 키와 값의 쌍으로 데이터를 저장하거나, 키 자체를 값으로 사용하여 데이터를 저장하는 컨테이너이다. 시퀀스 컨테이너가 순서에 따라 요소를 관리하는 것과 달리, 연관 컨테이너는 키를 기반으로 요소를 빠르게 검색, 삽입, 삭제하는 데 최적화되어 있다. 내부적으로 균형 이진 탐색 트리나 해시 테이블과 같은 자료 구조를 사용하여 구현된다.

주요 연관 컨테이너로는 std::set, std::map, std::multiset, std::multimap이 있다. std::set은 유일한 키의 집합을 저장하며, std::map은 유일한 키에 각각 하나의 값을 매핑하여 저장한다. multiset과 multimap은 각각 중복된 키를 허용하는 버전이다. 이들 컨테이너는 기본적으로 키를 기준으로 오름차순 정렬된 상태를 유지한다.

C++11 표준부터 도입된 비정렬 연관 컨테이너는 기존 정렬 연관 컨테이너와 다른 내부 구조를 가진다. std::unordered_set, std::unordered_map, std::unordered_multiset, std::unordered_multimap이 이에 해당하며, 내부적으로 해시 함수를 사용하는 해시 테이블로 구현된다. 이들은 요소의 순서를 보장하지 않지만, 일반적으로 평균적인 검색, 삽입, 삭제 성능이 더 빠르다.

연관 컨테이너의 선택은 데이터의 특성과 필요한 연산에 따라 결정된다. 키의 정렬이 필요하거나 범위 기반 질의가 빈번한 경우에는 정렬 연관 컨테이너를, 최대한의 검색 속도가 중요하고 순서가 필요 없는 경우에는 비정렬 연관 컨테이너를 사용하는 것이 일반적이다. 모든 연관 컨테이너는 반복자를 통해 요소에 접근할 수 있으며, 알고리즘 라이브러리와 함께 사용될 수 있다.

컨테이너 어댑터는 기존 시퀀스 컨테이너의 인터페이스를 제한하거나 변형하여 특정 자료 구조의 동작 방식을 제공하는 클래스 템플릿이다. 이들은 독립적인 컨테이너가 아니라 다른 컨테이너를 내부적으로 감싸서(어댑터 패턴) 새로운 추상화 계층을 제공한다. 주로 스택, 큐, 우선순위 큐와 같은 제한된 접근 방식을 필요로 하는 자료 구조를 구현하는 데 사용된다.

주요 컨테이너 어댑터로는 std::stack, std::queue, std::priority_queue가 있다. std::stack은 후입선출(LIFO) 방식으로 동작하며, 기본적으로 std::deque를 내부 컨테이너로 사용한다. std::queue는 선입선출(FIFO) 방식을 따르며, std::deque 또는 std::list를 기반으로 할 수 있다. std::priority_queue는 가장 높은 우선순위를 가진 요소에 항상 접근할 수 있도록 하며, 내부적으로 힙 자료 구조를 유지하기 위해 std::vector를 주로 사용한다.

이러한 어댑터들은 기반이 되는 내부 컨테이너의 특정 연산들(예: push_back, pop_back, front)만을 활용하여 자신의 인터페이스(push, pop, top)를 제공한다. 따라서 사용자는 스택이나 큐의 표준적인 동작에만 집중할 수 있으며, 내부 구현의 복잡성으로부터 자유롭다. 템플릿 매개변수를 통해 사용할 내부 컨테이너의 타입을 지정할 수 있어 일정한 유연성을 제공한다.